package dfs;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ThreeSum15 {
    @Test
    public void test() {
        threeSum(new int[]{-1,0,1,2,-1,-4});
    }

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> results = kSum(nums, 0, 3, 0);
        System.out.format("nums: %s, target: %d, results: %s\n", Arrays.toString(nums), 0, results);
        return results;
    }

    public static List<List<Integer>> kSum(int[] nums, int startIndex, int k, int target) {
        if (k == 2) {
            return twoSum(nums, startIndex, target);
        }

        List<List<Integer>> results = new ArrayList<>();
        int i = startIndex;

        while(i < nums.length-k+1) {
            List<List<Integer>> kMinus1SumResults = kSum(nums, i+1, k-1, target-nums[i]);
            for (List<Integer> kMinus1SumResult: kMinus1SumResults) {
                kMinus1SumResult.add(nums[i]);
                results.add(kMinus1SumResult);
            }

            // 注意跳过相同的
            int last = nums[i];
            i++;
            while (i < nums.length-k+1 && nums[i] == last) {
                i++;
            }
        }
        return results;
    }

    public static List<List<Integer>> twoSum(int[] nums, int startIndex, int target) {
        int i = startIndex;
        int j = nums.length - 1;

        List<List<Integer>> results = new ArrayList<>();

        while (i < j) {
            int sum = nums[i] + nums[j];
            if (sum == target) {
                //System.out.format("nums: %s, target: %d, i, %d, index1: %d, j: %d, index2: %d\n", Arrays.toString(nums), target, i, array[i].index, j, array[j].index);
                List<Integer> result = new ArrayList<>();
                result.add(nums[i]);
                result.add(nums[j]);
                results.add(result);
            }
            // 注意跳过相同的
            if (sum < target) {
                int last = nums[i];
                i++;
                while(i < j && nums[i] == last) {
                    i++;
                }
            } else {
                int last = nums[j];
                j--;
                while(i < j && nums[j] == last) {
                    j--;
                }
            }
        }
        return results;
    }
}
